package leetcode_501_600;

import node.TreeNode;

public class LeeCode_543 {
    public static void main(String[] args) {
        System.out.println(diameterOfBinaryTree(new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3))));
    }
    private static int diameterOfBinaryTree(TreeNode root) {
        int[] ans = new int[1];
        int l = getD(root.left, 0, ans);
        int r = getD(root.right, 0, ans);
        return Math.max(ans[0], l + r);
    }
    private static int getD(TreeNode node, int depth, int[] max){
        if (node == null)
            return depth;
        int l = getD(node.left, depth + 1, max);
        int r = getD(node.right, depth + 1, max);
        int c1 = l - depth - 1;
        int c2 = r - depth - 1;
        max[0] = Math.max(max[0], c1 + c2);
        return Math.max(l, r);
    }
}
